/**
 * 反转链表
 */

// 链表定义
function LinkedList(val, next) {
    return {val, next}
}

// 将链表转换为list
function toList(head) {
    var result = []
    function traverse(head) {
        if (head == undefined) {
            return
        }
        result.addLast(head.val)
        traverse(head.next)
    }
    traverse(head)
    return result
}

// 反转链表
function reverse(head) {
    if (head == undefined || head.next == undefined) {
        return head
    }
    var p = head.next
    var q = reverse(head.next)
    p.next = head
    head.next = undefined
    return q
}

var head = LinkedList(1, LinkedList(2, LinkedList(3, LinkedList(4, LinkedList(5)))))
println(toList(head))
println(toList(reverse(head)))
